Graphs are often used in the fields of mathematics and computer science. A graph may include nodes, as well as edges connecting the nodes. An edge between two nodes may be associated, for example, with a cost to travel or traverse between the two nodes.
Graphs may be used to model many types of relationships. For example, a graph may be used to model a social network or a telecommunication network. Graphs may also be used to represent maps. For example, a graph may represent a road map, where each node of the graph represents a road intersection, and each edge of the graph represents a road segment linking two intersections. The cost associated with each edge may correspond to a distance and/or time it takes to travel between the two intersections. A mapping program may use the graph to calculate directions between two points or nodes.
It may be desirable to calculate a route between two points on a map. For example, a user may use the mapping program to determine a route for driving directions between two points. Using the map, the corresponding route may be highlighted or otherwise displayed. The route in the map can correspond to a route in a graph having nodes and edges connecting the nodes.
A user may also be interested in making one or more detours from a determined route to one or more points of interest (POIs) on the map, such as a hotel, restaurant, hospital, gas station, or historical landmark. The POIs can be viewed as destination nodes in the graph that are not part of the route. The user may want to determine the fastest or shortest path to get from the determined route to the POIs. For example, if the user is driving, the user may seek the closest gas station or fast food restaurant off the route.
There are several known algorithms for calculating distances between nodes of a graph, such as: Dijkstra's algorithm, Moore's algorithm, Floyd-Warshall's algorithm, Bellman-Ford's algorithm, and Johnson's algorithm. However, these algorithms perform multiple iterations and are too costly or inefficient for the purpose of calculating costs or a shortest path from points along a route in a graph to a destination node (POI). Indeed, there may be a very large number of origin nodes from which a user may depart from the route, and a large number of destination nodes.
Accordingly, there is a need for improved systems and methods for analyzing one or more destination nodes, including the ability to analyze costs and determine a shortest distance from points along a route to at least one destination node or point. More generally, there is also a need to provide more efficient algorithms for calculating costs or distances between nodes on a graph when determining a route or path.